package com.practice.niuke.new_direct_practice.class11;

/**
 * 给定一个整数 n，返回从 1 到 n 的数字中 1 出现的个数。
 * 例如: n=5，1~n 为 1，2，3，4，5。那么 1 出现了 1 次，
 * 所以返回 1。 n=11，1~n 为 1，2，3，4，5，6，7，8，9，10，11。
 * 那么 1 出现的次数为 1(出现 1 次)，10(出现 1 次)，11(有两个 1，所以出现了 2 次)，所以返回 4。
 */
public class Code03_OneNumber {

	public static int solution1(int num) {
		if (num < 1) {
			return 0;
		}
		int count = 0;
		for (int i = 1; i != num + 1; i++) {
			count += get1Nums(i);
		}
		return count;
	}

	public static int get1Nums(int num) {
		int res = 0;
		while (num != 0) {
			if (num % 10 == 1) {
				res++;
			}
			num /= 10;
		}
		return res;
	}

	/**
	 * 课程中的讲解的方法（TODO）
	 *
	 * @param num
	 * @return
	 */
	public static int solution2(int num) {
		if (num < 1) {
			return 0;
		}
		int len = getLenOfNum(num);
		if (len == 1) {
			return 1;
		}
		// 13765 --> num
		// 10000 --> tmp1
		// 7812278127 ---> num
		// 1000000000 ---> tmp1, 若num有K位， tmp1 = 10^(K-1), tmp1/10 = 10^(K-2),
		// 下面的len就是K
		int tmp1 = powerBaseOf10(len - 1);
		// first为最高位的数
		int first = num / tmp1;
		// （1）最高位有几个1，分情况：
		// （1.1）最高位的数字为1，firstOneNum = num % 10^(K-1) + 1；
		// （1.2）最高位的数字不为1,firstOneNum = 10^(K-1)
		int firstOneNum = first == 1 ? num % tmp1 + 1 : tmp1;
		// （2）其他位有几个1，otherOneNum = first * (K-1) * 10^(k-2)
		int otherOneNum = first * (len - 1) * (tmp1 / 10);
		return firstOneNum + otherOneNum
				  // 递归行为
				+ solution2(num % tmp1);
	}

	public static int getLenOfNum(int num) {
		int len = 0;
		while (num != 0) {
			len++;
			num /= 10;
		}
		return len;
	}

	public static int powerBaseOf10(int base) {
		return (int) Math.pow(10, base);
	}

	public static void main(String[] args) {
		int num = 50000000;
		long start1 = System.currentTimeMillis();
		System.out.println(solution1(num));
		long end1 = System.currentTimeMillis();
		System.out.println("cost time: " + (end1 - start1) + " ms");

		long start2 = System.currentTimeMillis();
		System.out.println(solution2(num));
		long end2 = System.currentTimeMillis();
		System.out.println("cost time: " + (end2 - start2) + " ms");

	}
}
